package com.mlamp.查找算法;

import com.mlamp.排序算法.基础排序;
import com.mlamp.排序算法.快速排序;

import java.util.Arrays;

public class 二分查找寻找左右边界 {

    public static void main(String[] args) {
        /*int[] ints = 基础排序.generateArray(30);
        int[] ints1 = 快速排序.quickSort(ints, 0, ints.length - 1);
        System.out.println(Arrays.toString(ints1));
        for (int i = 0; i < ints1.length; i++) {
            int i1 = halfQuery(ints1, ints1[i]);
            System.out.println(String.format("target [%d] at loc %d", ints1[i], i1));
        }
        for (int i = 0; i < ints1.length; i++) {
            int i1 = recursiveHalfQuery(ints1, ints1[i], 0, ints1.length - 1);
            System.out.println(String.format("target [%d] at loc %d", ints1[i], i1));
        }*/
        int[] input = new int[]{
                3, 7, 10, 10, 12, 12, 17, 42, 43, 44, 59, 65, 66, 85, 87, 88, 91, 99, 104, 105, 109, 125, 126, 155, 162, 163, 178, 183, 194, 195
        };
        int loc = halfQueryByRightBound(input, 10);
        System.out.println("loc = " + loc);

        input = new int[]{
                1, 2, 2, 2, 3, 3, 4
        };
        int left = leftBoundA(input, 2);
        System.out.println("left: " + left);
        int right = rightBountA(input, 2);
        System.out.println("left = " + left + ", and right= " + right);

        System.out.println("--------------------------------------");

        left = lbound(input, 3);
        System.out.println(left);

        right = rbound(input, 3);
        System.out.println(right);


        left = lboundA(input, 3);
        System.out.println(left);

        right = rboundA(input, 3);
        System.out.println(right);

        left = lboundB(input, 3);
        System.out.println(left);

        right = rboundB(input, 3);
        System.out.println(right);
    }

    public static int lboundB(int[] array, int target) {
        assert array != null : "array is null";
        assert array.length > 0 : "array is empty";
        int left = 0, right = array.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (array[mid] == target) right = mid;
            else if (array[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (left == array.length) return -1;
        else return array[left] == target ? left : -1;
    }


    public static int lboundA(int[] array, int target) {
        if (array == null || array.length == 0) return -1;
        int left = 0, right = array.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (array[mid] == target) right = mid;
            else if (array[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (left == array.length) return -1;
        else return array[left] == target ? left : -1;
    }


    public static int rboundB(int[] array, int target) {
        assert array != null : " array is null";
        assert array.length > 0 : "array is empty";
        int left = 0, right = array.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (array[mid] == target) left = mid + 1;
            else if (array[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (left == 0) return -1;
        else return array[left - 1] == target ? left - 1 : -1;
    }

    public static int rboundA(int[] array, int target) {
        if (array == null || array.length == 0) return -1;
        int left = 0, right = array.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (array[mid] == target) left = mid + 1;
            else if (array[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (left == 0) return -1;
        else return array[left - 1] == target ? left - 1 : -1;
    }


    public static int lbound(int[] array, int target) {
        if (array == null || array.length == 0) throw new IllegalArgumentException("invalid array given");
        int lo = 0, hi = array.length, mid = -1;
        while (lo < hi) {
            mid = lo + ((hi - lo) >> 1);
            if (array[mid] == target) {
                hi = mid;//注意这里
            } else if (array[mid] < target) {
                lo = mid + 1;
            } else hi = mid;//注意这里
        }
        if (lo == array.length) return -1;
        else return array[lo] == target ? lo : -1;
    }

    public static int rbound(int[] array, int target) {
        if (array == null || array.length == 0) throw new IllegalArgumentException("invalid array given");
        int lo = 0, hi = array.length, mid = -1;
        while (lo < hi) {
            mid = lo + ((hi - lo) >> 1);
            if (array[mid] == target) lo = mid + 1;
            else if (array[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        if (lo == 0) return -1;
        else return array[lo - 1] == target ? lo - 1 : -1;
    }


    public static int leftBoundA(int[] array, int target) {
        if (array == null || array.length < 1) throw new IllegalArgumentException("invalid array given");
        int lo = 0, hi = array.length - 1, mid = -1;
        while (lo < hi) {
            mid = lo + ((hi - lo) >> 1);
            if (array[mid] == target) {
                hi = mid;
            } else if (array[mid] > target) {
                hi = mid - 1;
            } else if (array[mid] < target) {
                lo = mid + 1;
            }
        }
        if (array[lo] == target) return lo;
        else return -1;
    }

    public static int rightBountA(int[] array, int target) {
        if (array == null || array.length < 1) throw new IllegalArgumentException("invalid array given");
        int lo = 0, hi = array.length - 1, mid = -1;
        while (lo < hi) {
            mid = lo + ((hi - lo) >> 1);
            if (array[mid] == target) {
                lo = mid;
            } else if (array[mid] > target) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        if (array[lo] == target) return lo;
        else return -1;
    }


    //[3, 7, 10, 10, 12, 12, 17, 42, 43, 44, 59, 65, 66, 85, 87, 88, 91, 99, 104, 105, 109, 125, 126, 155, 162, 163, 178, 183, 194, 195]
    public static int halfQueryByLeftBound(int[] array, int target) {
        int low = 0, high = array.length - 1, mid = -1;
        while (low < high) {
            mid = low + (high - low) / 2;
            if (array[mid] == target) high = mid;
            else if (array[mid] > target) {
                high = mid - 1;
            } else low = mid + 1;
        }
        if (array[low] == target) return low;
        return -1;
    }


    public static int leftBound(int[] array, int target) {
        int low = 0, hi = array.length - 1;
        int mid = -1;
        while (low < hi) {
            mid = low + ((hi - low) >> 1);
            if (target == array[mid]) {
                hi = mid;
            } else if (target > array[mid]) {
                hi = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        if (array[low] == target) return low;
        return -1;
    }

    public static int rightBound(int[] array, int target) {
        int low = 0, hi = array.length - 1;
        int mid = -1;
        while (low < hi) {
            mid = low + ((hi - low) >> 1);
            if (target == array[mid]) low = mid;
            else if (target > array[mid]) low = mid + 1;
            else hi = mid - 1;
        }
        if (array[low] == target) return low;
        return -1;
    }


    public static int bqLeftBound(int[] array, int target) {
        int low = 0, hi = array.length - 1;
        int mid = -1;
        while (low < hi) {
            mid = low + ((hi - low) >> 1);
            if (array[mid] == target) hi = mid;
            else if (array[mid] < target) low = mid + 1;
            else hi = mid - 1;
        }
        if (array[low] == target) return low;
        return -1;
    }

    public static int bqRightBound(int[] array, int target) {
        int low = 0, hi = array.length - 1;
        int mid = -1;
        while (low < hi) {
            mid = low + ((hi - low) >> 1);
            if (target == array[mid]) low = mid;
            else if (target > array[mid]) low = mid + 1;
            else hi = mid - 1;
        }
        if (array[low] == target) return low;
        return -1;
    }


    public static int biQueryByLeftBound(int[] array, int target) {
        int low = 0, hi = array.length - 1, mid = -1;
        while (low < hi) {
            mid = low + ((hi - low) >> 1);
            if (target == array[mid]) hi = mid;
            else if (target > array[mid]) low = mid + 1;
            else hi = mid - 1;
        }
        if (array[low] == target) return low;
        return -1;
    }

    public static int biQueryByRightBound(int[] array, int target) {
        int low = 0, hi = array.length - 1, mid = -1;
        while (low < hi) {
            mid = low + ((hi - low) >> 1);
            if (target == array[mid]) low = mid;
            else if (target > array[mid]) low = mid + 1;
            else hi = mid - 1;
        }
        if (array[low] == target) return low;
        return -1;
    }


    //[3, 7, 10, 10, 12, 12, 17, 42, 43, 44, 59, 65, 66, 85, 87, 88, 91, 99, 104, 105, 109, 125, 126, 155, 162, 163, 178, 183, 194, 195]
    public static int halfQueryByRightBound(int[] array, int target) {
        int low = 0, high = array.length - 1, mid = -1;
        while (low < high) {
            mid = low + (high - low) / 2;
            if (array[mid] == target) low = mid;
            else if (array[mid] > target) {
                high = mid - 1;
            } else low = mid + 1;
        }
        if (array[low] == target) return low;
        return -1;
    }

    public static int halfQuery(int[] array, int target) {
        int low = 0, high = array.length - 1, mid = -1;
        while (low <= high) {
            mid = low + (high - low) / 2;
            if (array[mid] == target) return mid;
            else if (array[mid] > target) {
                high = mid - 1;
            } else low = mid + 1;
        }
        return mid;
    }

    public static int recursiveHalfQuery(int[] array, int target, int start, int end) {
        int mid = start + ((end - start) >> 1);
        if (target == array[mid]) return mid;
        if (target < array[mid]) return recursiveHalfQuery(array, target, start, mid - 1);
        if (target > array[mid]) return recursiveHalfQuery(array, target, mid + 1, end);
        return -1;
    }
}
